/**
 * 分治法- 分而治之
 * 
 * 工作原理：
 * 1、设定一条基线
 * 2、根据此基线可以不停将问题进行分解，直到所有内容符合基线标准
 * 
 */

const quickSort = function (arr) {
  if (arr.length <= 1) {
    return arr
  }

  const pivotIndex = Math.floor(arr.length / 2)
  const pivot = arr.splice(pivotIndex, 1)[0]
  let left = []
  let right = []

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }

  return quickSort(left).concat([pivot], quickSort(right))
}

// var arr = [2,3,1,4,9,8,7,10,20,11]
// var arr1 = quickSort(arr)
// console.log(arr1)

/**
 * 贪婪 利益最大化 始终查找最大的项目， 尽可能快满足需求
 * 
 * 给定一个整数数组nums， 找到一个具有最大和的连续子数组 返回其最大和
 * 
 * 何时适用贪婪： 需要查找最大项目等类型， 同时满足利益最大化
 * 
 */


const maxSubArray = function (inputArr) {
  if (inputArr.length <= 1) return inputArr
  let result = inputArr[0]
  let sum = 0
  for (const num of inputArr) {
    // console.log(num)
    if (sum > 0) {
      sum += num
    } else {
      sum = num
    }
    result = Math.max(sum, result)
  }
  return result
}


// var arr = [-2, 3, 0, -4, 2, 1, -1]
// var arr1 = maxSubArray(arr)
// console.log(arr1)

/**
 * 动态规划（何时适用动态规划）---- 将待求解的问题分解成若干子问题：子问题之间相互有联系
 * F(0)= 0 F(1) =1
 * F(n) = F(n-1) + F(n-2), 其中n>1
 * 
 * 
 */

const fib = function (n) {
  if (n < 2) return n
  let pre = 0
  let next = 0
  let res = 1
  for(let i=2;i<n;i++){
    pre = next
    next = res
    res = pre + next
  }
  return res
}

var number = fib(9)
console.log(number)


/**
 *  图  与 图算法
 *  构成： 边集合  + 顶点集合
 *  分类： 有向图、无向图、构造图（复合引用）
 * 
 *  试题： 实现图类
 * 
 */ 

class Graph {

}